#pragma once

#include <functional>
#include <vector>

#ifndef MAZE_CELL_DECLARED
#define MAZE_CELL_DECLARED
namespace Maze {

  /**
   * @brief 迷宫中的网格坐标。
   *
   *  - row 表示行索引，从 0 开始。
   *  - col 表示列索引，从 0 开始。
   */
  struct Cell {
    int row{0};
    int col{0};

    friend constexpr bool operator==(const Cell& lhs, const Cell& rhs) noexcept {
      return lhs.row == rhs.row && lhs.col == rhs.col;
    }
  };

} // namespace Maze
#endif // MAZE_CELL_DECLARED

namespace Maze {

  /**
   * @brief 使用深度优先搜索寻找从 (0,0) 至 (rows-1, cols-1) 的路径。
   *
   * @param maze 仅包含 0/1 的二维网格，0 表示可走，1 表示障碍。
   * @return 若存在路径则返回节点序列，否则返回空向量。
   *
   * @note 搜索顺序固定为“右→下→左→上”，因此不保证得到最短路径。
   */
  inline auto depthFirstSearch(const std::vector<std::vector<int>>& maze)
      -> std::vector<Cell> {
    if (maze.empty() || maze[0].empty()) {
      return {};
    }

    const int rows = static_cast<int>(maze.size());
    const int cols = static_cast<int>(maze[0].size());
    std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
    std::vector<Cell> path;

    /**
     * @brief 判断坐标是否可通行。
     */
    auto isValid = [&](int r, int c) noexcept {
      return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;
    };

    /**
     * @brief 递归回溯：按固定方向顺序尝试四个相邻格。
     */
    std::function<bool(int, int)> dfs = [&](int r, int c) -> bool {
      if (!isValid(r, c) || visited[r][c]) {
        return false;
      }
      visited[r][c] = true;
      path.push_back({r, c});

      if (r == rows - 1 && c == cols - 1) {
        return true; ///< 抵达终点，停止搜索。
      }

      constexpr int DR[4] = {0, 1, 0, -1};
      constexpr int DC[4] = {1, 0, -1, 0};
      for (int i = 0; i < 4; ++i) {
        if (dfs(r + DR[i], c + DC[i])) {
          return true; ///< 只要某条路径成功便立刻返回。
        }
      }

      path.pop_back(); ///< 四邻皆不可达时回溯撤销当前节点。
      return false;
    };

    if (dfs(0, 0)) {
      return path;
    }
    return {};
  }

} // namespace Maze